package pro.softzhang.algo.lc800;

import pro.softzhang.algo.flag.book.BDaily;
import pro.softzhang.algo.flag.knowledge.KDynamicPlanning;

@BDaily(20221010)
@KDynamicPlanning
public class LC801_MinimumSwapsToMakeSequenceIncreasing {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Solution {
        public int minSwap(int[] nums1, int[] nums2) {
            int length = nums1.length;
            int[][] dp = new int[2][2];
            dp[0][1] = 1;
            for (int i = 1; i < length; i++) {
                int a = length + 10, b = a;
                int pre = (i - 1) & 1, cur = i & 1;
                if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
                    a = dp[pre][0];
                    b = dp[pre][1] + 1;
                }

                if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
                    a = Math.min(a, dp[pre][1]);
                    b = Math.min(b, dp[pre][0] + 1);
                }

                dp[cur][0] = a; dp[cur][1] = b;
            }
            return Math.min(dp[(length - 1) & 1][0], dp[(length - 1) & 1][1]);
        }
    }
}
